LeetCode 977. Squares of a Sorted Array

977.Squares of a Sorted Array（有序数组的平方）

链接

https://leetcode-cn.com/problems/squares-of-a-sorted-array/

题目

给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

　　输入：[-4,-1,0,3,10]
　　输出：[0,1,9,16,100]

示例 2：

　　输入：[-7,-3,2,3,11]
　　输出：[4,9,9,49,121]

提示：

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。

思路

非递减顺序，再加上存在负数，可以通过在两端比较：先取head和tail表示两端的位置，比较两个数的平方，平方较大者，放到新数组的靠后位置。

（真要偷懒可以直接用sort，但是这样就没啥意义了）

代码

public int[] sortedSquares(int[] A) {
  int len = A.length;
  int head = 0;
  int tail = len - 1;
  int[] B = new int[len];
  while (head <= tail) {
    len--;
    int i = A[head] * A[head];
    int j = A[tail] * A[tail];
    if (i > j) {
      B[len] = i;
      head++;
    } else {
      B[len] = j;
      tail--;
    }
  }
  //     B = B.reverse
  return B;
}